package xyz.scootaloo.oj.leetcode

import org.junit.Test
import xyz.scootaloo.common.TestDsl

/**
 * @author flutterdash@qq.com
 * @since 2021/7/2 21:08
 */
class P278 : VersionControl(), TestDsl {
    override fun firstBadVersion(n: Int) : Int {
        var left = 0
        var right = n
        while (left < right) {
            val mid = left + (right - left).shr(1)
            if (isBadVersion(mid)) {
                right = mid
            } else {
                left = mid + 1
            }
        }

        return left
    }

    @Test
    fun test0() {
        badVersion = 3
        firstBadVersion(5) shouldBe 3
        badVersion = 1702766719
        firstBadVersion(2126753390) shouldBe 1702766719
    }
}

open class VersionControl {
    var badVersion: Int = 0

    fun isBadVersion(version: Int): Boolean {
        return version >= badVersion
    }

    open fun firstBadVersion(n: Int): Int {
        return -1
    }
}
